package com.dbh.alg.datastructure;


/**
 * 删除链表中的重复元素
 * @author dongbanghui
 * @date 2025/5/9
 */
public class E04Leetcode83 {

    /**
     * 删除链表中的重复元素 - 双指针法
     * @param head 链表头节点
     * @return 删除后的链表头节点
     */
    public static ListNode deleteDuplicates(ListNode head){
        if (head == null || head.next == null) {
            return head;
        }
        ListNode s = new ListNode(-1, head);
        ListNode p1 = s;
        ListNode p2;
        while ((p2 = p1.next) != null) {
            if (p1.val == p2.val) {
                // 删除重复元素
                p1.next = p2.next;
            } else {
                // 向后平移
                p1 = p1.next;
            }
        }
        return s.next;
    }

    /**
     * 删除链表中的重复元素 - 递归法
     * @param p 链表头节点
     * @return 删除后的链表头节点
     */
    public static ListNode deleteDuplicates2(ListNode p) {
        if (p == null || p.next == null) {
            return p;
        }
        // 如果当前节点和下一个节点的值相同
        if (p.val == p.next.val) {
            // 删除重复元素
            p.next = p.next.next;
            // 递归调用
            deleteDuplicates2(p);
        } else {
            // 向后平移
            deleteDuplicates2(p.next);
        }
        return p;
    }


    public static void main(String[] args) {
        ListNode o = ListNode.of(1, 1, 2, 3, 3, 4, 7);
        ListNode head = deleteDuplicates2(o);
        System.out.println(head);
    }

}
